package string;

/**
 165. Compare Version Numbers
 Medium

 Share
 Compare two version numbers version1 and version2.
 If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0.

 You may assume that the version strings are non-empty and contain only digits and the . character.

 The . character does not represent a decimal point and is used to separate number sequences.

 For instance, 2.5 is not "two and a half" or "half way to version three", it is the fifth second-level revision of the second first-level revision.

 You may assume the default revision number for each level of a version number to be 0. For example, version number 3.4 has a revision number of 3 and 4 for its first and second level revision number. Its third and fourth level revision number are both 0.

 Example 1:

 Input: version1 = "0.1", version2 = "1.1"
 Output: -1
 Example 2:

 Input: version1 = "1.0.1", version2 = "1"
 Output: 1
 Example 3:

 Input: version1 = "7.5.2.4", version2 = "7.5.3"
 Output: -1
 Example 4:

 Input: version1 = "1.01", version2 = "1.001"
 Output: 0
 Explanation: Ignoring leading zeroes, both “01” and “001" represent the same number “1”
 Example 5:

 Input: version1 = "1.0", version2 = "1.0.0"
 Output: 0
 Explanation: The first version number does not have a third level revision number, which means its third level revision number is default to "0"


 Note:

 Version strings are composed of numeric strings separated by dots . and this numeric strings may have leading zeroes.
 Version strings do not start or end with dots, and they will not be two consecutive dots.
 */
public class Q165_CompareVersionNumbers {

    private int compareVersion(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        int v1pos = 0;
        int v2pos = 0;
        while (v1pos<v1.length || v2pos<v2.length) {
            int n1 = v1pos<v1.length? Integer.parseInt(v1[v1pos]): 0;
            int n2 = v2pos<v2.length? Integer.parseInt(v2[v2pos]): 0;
            if (n1 > n2) {
                return 1;
            } else if (n1 < n2) {
                return -1;
            }
            v1pos++;
            v2pos++;
        }
        return 0;
    }

    /**
     * Compare Version Numbers Optimization
     */
    private int compareVersionOpt(String version1, String version2) {
        String[] v1 = version1.split("\\.");
        String[] v2 = version2.split("\\.");
        int v1pos = 0;
        int v2pos = 0;
        while (v1pos<v1.length || v2pos<v2.length) {
            String n1 = v1pos<v1.length? v1[v1pos]: "0";
            String n2 = v2pos<v2.length? v2[v2pos]: "0";
            int res = compare(n1, n2);
            if (res != 0) {
                return res;
            }
            v1pos++;
            v2pos++;
        }
        return 0;
    }
    private int compare(String str1, String str2) {
        String s1 = removeLeadingZero(str1);
        String s2 = removeLeadingZero(str2);
        if (s1.length() > s2.length()) {
            return 1;
        } else if (s1.length() < s2.length()) {
            return -1;
        } else {
            int s1pos = 0;
            int s2pos = 0;
            int len = s1.length();
            while (s1pos<len) {
                if (s1.charAt(s1pos) > s2.charAt(s2pos)) {
                    return 1;
                } else if (s1.charAt(s1pos) < s2.charAt(s2pos)) {
                    return -1;
                }
                s1pos++;
                s2pos++;
            }
        }
        return 0;

    }
    private String removeLeadingZero(String str) {
        int start = 0;
        for (int i=0; i<str.length(); i++) {
            if (str.charAt(i) == '0') {
                start++;
            } else {
                return str.substring(start);
            }
        }
        return start==str.length()?"0": str.substring(start);
    }

    public static void main(String[] args) {
        Q165_CompareVersionNumbers q165_compareVersionNumbers = new Q165_CompareVersionNumbers();
        int res = q165_compareVersionNumbers.compareVersionOpt("1.0", "1.0.0");
        System.out.println(res);
        int res1 = q165_compareVersionNumbers.compareVersionOpt("1.01", "1.001");
        System.out.println(res1);
        int res2 = q165_compareVersionNumbers.compareVersionOpt("7.5.2.4", "7.5.3");
        System.out.println(res2);
    }
}
